package com.ankie.algorithm;

import java.util.Arrays;

/**
 * @author :  zhongyu
 * Create at:  2020/6/23 15:08
 * Copyright: (c)2019 AIR Times Inc. All rights reserved.
 * @version : 1.0
 */
public class ConstructBinaryTree2 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[0]);
        int index = findIndex(inorder, root.val);
        if (index == -1) {
            return root;
        }

        // 处理左子树
        int[] leftPreOrder = Arrays.copyOfRange(preorder, 1, index + 1);
        int[] leftInOrder = Arrays.copyOfRange(inorder, 0, index);
        root.left = buildTree(leftPreOrder, leftInOrder);

        // 处理右子树
        int[] rightPreOrder = Arrays.copyOfRange(preorder, index + 1, preorder.length);
        int[] rightInOrder = Arrays.copyOfRange(inorder, index + 1, inorder.length);

        root.right = buildTree(rightPreOrder, rightInOrder);
        return root;
    }

    private int findIndex(int[] order, int index) {
        for (int i = 0; i < order.length; i++) {
            if (order[i] == index) {
                return i;
            }
        }
        return -1;
    }
}
